// TopSort.cpp : 定义控制台应用程序的入口点。
//拓扑排序算法-TopSort

#include "stdafx.h"
#include "iostream"
using namespace std;
const int MaxSize = 20;
static int visited[MaxSize] = { 0 };
struct ArcNode
{
	int adjvex;
	ArcNode *next;
};
template<class DataType>
struct VertexNode
{
	int in;
	DataType vertex;
	ArcNode *firstedge;
};

template<class DataType>
class ALGraph
{
public:
	ALGraph(int b[], DataType a[], int n, int e);
	~ALGraph();
	friend void TopSort(ALGraph<char> G);
private:
	VertexNode<DataType> adjlist[MaxSize];
	int vertexNum, arcNum;

};

//构造函数
template<class DataType>
ALGraph<DataType>::ALGraph(int b[], DataType a[], int n, int e)
{
	vertexNum = n;
	arcNum = e;
	for (int i = 0; i < vertexNum; i++)
	{
		adjlist[i].in = b[i];
		adjlist[i].vertex = a[i];
		adjlist[i].firstedge =NULL;
	}
	cout << "请输入每条边的两个邻接点：" << endl;
	for (int k = 0; k < arcNum; k++)
	{
		int i, j;
		cin >> i >> j;
		ArcNode *s = new ArcNode;
		s->adjvex = j;
		s->next = adjlist[i].firstedge;
		adjlist[i].firstedge = s;
	}
}

//析构函数
template<class DataType>
ALGraph<DataType>::~ALGraph()
{
	for (int i = 0; i < vertexNum; i++)
	{
		if (adjlist[i].firstedge != NULL)
			delete adjlist[i].firstedge;
	}
}

//TopSort算法
void TopSort(ALGraph<char> G)
{
	int top = -1;
	int count = 0;
	int S[MaxSize];
	for (int i = 0; i < G.vertexNum; i++)
	{
		if (G.adjlist[i].in == 0)
			S[++top] = i;
	}
	while (top != -1)
	{
		int j = S[top--];
		cout << G.adjlist[j].vertex<<" ";
		count++;
		ArcNode *p = G.adjlist[j].firstedge;
		while (p != NULL)
		{
			int k = p->adjvex;
			G.adjlist[k].in--;
			if (G.adjlist[k].in == 0)
				S[++top] = k;
			p = p->next;
		}
	}
	if (count < G.vertexNum)
		cout << "有回路！" << endl;
}

int main()
{
	//输入：1 0 3 0 2 0 1 3 2 3 4 3 3 5 4 5 4 2
	char a2[6] = { 'a','b','c','d','e','f' };
	int in2[6] = { 3,0,1,2,0,2 };
	ALGraph<char> A(in2, a2, 6, 9);
        cout<<"拓扑序列：";
	TopSort(A);
	return 0;
}